// https://www.lintcode.cn/problem/4-keys-keyboard/description?_from=ladder&&fromId=86

class Solution {
public:
    /**
     * @param N: an integer
     * @return: return an integer
     */
     
// Example 1:
// Input: 3
// Output: 3
// Explanation: A, A, A
// Example 2:
// Input: 7
// Output: 9
// Explanation: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V 
     
    // int maxA(int N) {
    //     if (N <= 3) return N;
    //     else 
    //     {
    //         int tmp = 3 * pow(2, N / 3 - 1);
    //         return tmp + tmp / 2 * (N % 3);
    //     }
    // }
    // 不是越早复制粘贴越好，而是越确保在最后一步粘贴越好。但也可能是倒数第二个的三倍更大。很多不确定性。
    
    
    // 一般都是考动态规划的，不太可能考直接推公式
    // 获得最优解的按键序列一定可以用以下两种子序列拼接而成:

    // 数个连续的 A
    // Ctrl-A + Ctrl-C + 数个连续的 Ctrl-V
    // 设定状态: f[i] 表示i次按键可以获得的最多数量的A
    
    // 我们的决策便是选用上面两种方案的哪一种, 枚举即可
    
    // 状态转移方程:
    
    // f[i] = max( f[i-1] + 1, f[i-2-j] * (j+1) )
    // 需要枚举j, 含义是连续按下了多少个 Ctrl-V
    
    // 边界: f[i] = i, i <= 4

    int maxA(int N) {
        vector<int> record(N + 1, 0);
        for (int i = 1; i <= N; ++i)
        {
            record[i] = record[i - 1] + 1;
            for (int j = 1; j + 2 < i; ++j)
            {
                record[i] = max(record[i], record[i - 2 - j] * (j + 1));
            }
        }
        for (auto r: record) cout << r << endl;
        return record[N];
    }
};